/**
 * https://leetcode-cn.com/problems/jump-game/
 * 跳跃游戏
 * 给定一个非负整数数组 nums, 你最初位于数组的 第一个下标, 数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标
 * @param nums
 */
const canJump = (nums: number[]):boolean => {
    const len = nums.length;

    // 可以达到右边的距离
    let rightDis = 0

    for (let i = 0; i < len; i++) {
        // 当前的索引小于最后达到的距离
        if (i <= rightDis) {
            // 更新距离右边的最大距离
            // 当前的索引加上长度就是距离右边的距离
            rightDis = Math.max(rightDis, i + nums[i])

            // 距离右边的距离大于等于的长度
            if (rightDis >= len - 1) {
                return true
            }
        }
    }

    return false
}


// error
const canJump2 = (nums: number[]): boolean => {
  const len = nums.length;

  let ans = false,
    hasFind = false;
  /**
   * @param next 下一个的位置
   * @param nextStep 下一个索引对应的值
   */
  const dfs = (next: number, nextStep: number) => {
    // 如果已经找到了或者长度超过数组的长度了, 函数不再执行
    if (hasFind || next > len) return;

    // 当前的索引加上要跳的步数刚好等于
    if (next === len) {
      ans = true;
      hasFind = true
      return;
    }


    for (let i = nextStep; i >= 1; i--) {
      // 跳跃
      dfs(next + i, nums[next + i - 1]);
    }
  };
  dfs(1, nums[0]);

  return ans;
};

console.log(canJump([2, 3, 1, 4]));
// console.log(canJump([1]));
// console.log(canJump([1, 2, 3]));
console.log(canJump([3, 2, 1, 1, 4]));